'''
解题思路

这是一道经典的二维前缀和的题目，首先需要知道前置知识就是在2维空间的前缀和如何计算？
在1维空间中，前缀和的公式非常简单，即(i, j)仅和当前点的值和前一个点所求和相关。
在2维空间中，我们是否也可以扩展开？即(i, j)与(i-1, j), (i, j-1), (i-1, j-1)的关系。
这里我们根据以前的正方形和长方形的公式可以得到：(i, j) = (i, j) + (i-1, j) + (i, j-1) - (i-1, j-1)

在获得这个公式后，我们就得到2维前缀和的数组，那么还有问题就是如何计算题目中的区间？其实这个可以
看作前缀和公式的扩展。计算前缀和公式我们相当计算了四个矩阵的关系，而这里我们需要将(i, j)扩展成一个矩形。
并且在扩展成矩形的同时，我们需要考虑它的范围，考虑到这些点，基本思路就清晰了。

1. 引入了2维前缀和的概念
2. 在2维前缀和的基础上扩展成广义前缀和【局部和】
3. 边界的问题
'''
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        ans = [[0] * n for _ in range(m)]
        presum = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                presum[i+1][j+1] = presum[i+1][j] + presum[i][j+1] - presum[i][j] + mat[i][j]

        for i in range(m):
            for j in range(n):
                r1, r2 = max(0, i - k), min(m - 1, i + k)
                c1, c2 = max(0, j - k), min(n - 1, j + k)
                ans[i][j] = presum[r2+1][c2+1] - presum[r2+1][c1] - presum[r1][c2+1] + presum[r1][c1]
        return ans
